'''
    合并k个链表
'''

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        '''
            可以使用两两合并的方法，先两个合并，然后再通过循环全部合并
        '''
        if not lists:
            return None
        arr = lists[0]
        for li in lists[1:]:
            arr = self.mergeTwoLists(arr,li)
        return arr


    def mergeTwoLists(self,headA,headB):
        newList = ListNode(-1)
        l = newList
        p,q = headA,headB
        while p and q:
            if p.val >= q.val:
                l.next = q
                q = q.next
            else:
                l.next = p 
                p = p.next
            l = l.next
        if p:
            l.next = p
        if q:
            l.next = q
        return newList.next
    
    def mergeKLists2(self, lists: List[ListNode]) -> ListNode:
        '''
            使用优先队列
        '''
        from typing import List
        import heapq
        if not lists:
            return None
        l = ListNode(-1)
        p = l
        pq = []
        for i in range(len(lists)):
            if lists[i]:
                heapq.heappush(pq,(lists[i].val,i))
                lists[i] = lists[i].next
        while pq:
            val,idx = heapq.heappop(pq)
            p.next = ListNode(val)
            p = p.next
            if lists[idx]:
                heapq.heappush(pq,(lists[idx].val,idx))
                lists[idx] = lists[idx].next
        return l.next
